1. Field of the Invention
The present invention relates generally to a system for tracking objects using GPS data; for example, tracking vehicles as they move over streets.
2. Description of the Related Art
A variety of automatic vehicle navigational systems have been developed and used to provide information about the actual location of a vehicle as it moves over streets. A common purpose of the vehicle navigational systems is to automatically maintain knowledge of the actual location of the vehicle at all times as it traverses the streets (i.e., track the vehicle). A given navigational system may be utilized in the vehicle to provide the vehicle operator with knowledge of the location of the vehicle and/or allow a central monitoring station to monitor the location of one or more vehicles.
For example, one general approach to such vehicle navigational systems is known as "dead reckoning," in which the vehicle is tracked by advancing a "dead reckoned position" from measured distances and headings. A system based upon dead reckoning principles may, for example, detect the distance traveled and heading of the vehicle using distance and heading sensors on the vehicle. The distance and heading data is processed by, for example, a computer using known equations to calculate a dead reckoned position of the vehicle. As the vehicle moves along a street, an old dead reckoned position is updated to a new or current dead reckoned position in response to the distance and heading data being provided by the sensors.
One problem with prior systems using dead reckoning is the accumulation of error that occurs as the dead reckoned positions are advanced. This error occurs, in part, as a result of inherent limitations on the achievable accuracy of the distance and heading sensors, which thus provide data that do not precisely identify the distance traveled nor the heading of the vehicle. Unless compensation for this error is made, the dead reckoned positions will become increasingly imprecise or inaccurate. Prior dead reckoning vehicle navigational systems have been developed and have attempted to solve this problem of the accumulation of error by providing additional information to the dead reckoned positions.
One example of additional information used to limit the error in a dead reckoning system is an electronic map. An electronic map consists of geographically referenced electronic data quantifying a physical, social or economic system. The range of information included in electronic maps is unlimited. For example, electronic maps could include data representing longitude, latitude, altitude, distances between elements, driving time, parcel numbers, tax information, tourist information, etc. Additionally, storing a map as a file on a computer allows for unlimited software applications to manipulate that data.
One example of a system that uses an electronic map is disclosed in U.S. Pat. No. 4,796,191, Vehicle Navigation System and Method. In this system, a dead reckoning component accepts raw sensor data and combines this data with history information to produce a new vehicle location from the previous location. This is the basic process of computing a distance traveled and a heading from the sensor data available. The available navigation sensors include differential odometers, vehicle odometers, compass, gyroscopes, inclinometers, defogger shunts and GPS receivers.
The vehicle odometer provides a count that represents distance traveled. The count can be cumulative and signed, so an increase represents travel in one direction, a decrease represents travel in the other direction. The count is proportional to some fraction of a wheel rotation.
The differential odometer is similar to the vehicle odometer. It gives distance traveled as a count that represents a fraction of a wheel rotation. It is a pair of sensors, one for the left wheel of a vehicle and one for the right wheel. Both sensors can be mounted on the front wheels or both sensors can be mounted on the back wheels. The left and right counts give not only distance traveled, but also relative heading. The difference between left and right wheel counts, combined with the physical dimensions of the vehicle, give the amount the vehicle has turned. This sensor is subject to low frequency drift when used to measure heading. It can appear that the vehicle is slowly turning when it is really going straight.
A gyroscope is another source of relative heading. It has properties similar to the differential wheel sensors. These sensors measure rate of turn per unit of time, so the signal may need to be integrated over time to obtain heading change.
A magnetic compass provides absolute heading information. The primary problem with a compass is that it is susceptible to high frequency noise. It also has problems with the variation in the magnetic environment caused by natural and man made objects. Bridges, overpasses, tunnels, and large steel frame buildings can cause severe interference with a compass. They can even remagnetize a vehicle. The flux gate compass measures the component of the earth's magnetic field that lies in the horizontal plane. It provides an x and y offset relative to some center point. This offset translates into a physical heading. As a result of the changing magnetic environment of a vehicle, this center and magnitude of the offset change with time and must be carefully tracked. Remagnetization of the vehicle may require recalibration of the compass. The absolute heading obtained from a compass can be combined with relative heading from differential wheel sensors or gyroscope to obtain a better heading than can be obtained from either type of sensor used alone. This is possible because the sensors have complimentary error properties, the compass does not drift and the relative heading sensors is not as susceptible to high frequency noise.
Inclination of the vehicle in hilly regions introduces error into the heading computed from the compass. The inclinometer allows the inclination to be measured and the compass heading to be corrected. The sensor provides pitch and roll signals proportional to the pitch and roll angles of the vehicle.
The defogger shunt provides correction to the compass heading for errors caused by vehicle generated magnetic fields. The name of the sensors derives from the most common example of a vehicle generated magnetic field, the rear window defogger circuit. A defogger shunt detects the operation and strength of the magnetic field. Calibration of the defogger determines the vector and scale to associate with this input for compass correction.
Dead reckoning uses a combination of a subset of the above-described sensors to determine the position of the vehicle being tracked. Dead reckoning contains error that grows with time and/or distance. To know where we are on a particular road network and to keep the dead reckoning errors bounded, at least one prior art system uses map matching.
Map matching uses an electronic map database (which includes street information) and the output of dead reckoning to derive a new position on the road network, when possible. Updating a vehicle position on the map in this manner produces high quality navigation and provides feedback to dead reckoning that helps maintain sensor calibration.
Although the above-described system provides an accurate navigational tool, such a system can be expensive. As described above, the system requires a combination of a number of sensors and specialized electronics. No one sensor or combination has traditionally been able to supply sufficient data to reliably derive a dead reckoned position. As more sensors are used, the accuracy of the system increases; however, the system becomes more sophisticated and the cost of the system increases. Since prior art navigation systems use many sensors, these systems are very expensive. Another problem with the above described system is that it is difficult to install, maintain and calibrate the sensors on an automobile.
Additionally, navigation performance for the above described system can degrade if the map matching relocates the vehicle's position to an incorrect road. This can occur because of an extreme anomalous magnetic field, wheel slippage or map errors. Another disadvantage arises if the difference between the computed vehicle position and the nearest appropriate road is too large, i.e. exceeds a predetermined allowable error estimate. Under these circumstances the dead reckoning system will not update its position. Once an incorrect update has been made or the errors become too large, precision navigation may not be automatically regained without manual intervention. Another disadvantage of some prior art navigation systems is that they typically require that the operation of the system be visually monitored by the operator and manually calibrated and that, after calibration, correct initial position information be entered manually.
Another prior art navigational system tracks vehicles using GPS data. Based on the GPS data, the system determines a two or three dimensional location of the vehicle. This location is then superimposed on a map. There is no map matching process used to coordinate the display of the vehicle's location to a street, and the GPS data tends to jump and be unreliable.
Another prior art system uses the dead reckoning and map matching process described above (with respect to U.S. Pat. No. 4,790,191) in combination with GPS sensors. That is, when the relative navigation sensors described above (vehicle odometer, differential odometer . . . ) are providing data within an acceptable error, the system does not use the GPS data to update the vehicle's position. The system does use GPS data to test whether the data from the relative sensors are within the acceptable error. If not, the system resets the vehicle's position to a position calculated based on the GPS data and then the system performs a dead reckoning cycle followed by map matching. This system can be expensive, and difficult to install, maintain and calibrate.